About Us Services Blog Contact Us Learn
Home > DSA Graphs > Detecting a Cycle in an Undirected Graph - DSA

Detecting a Cycle in an Undirected Graph - DSA

Posted by R.A.S CODERS
DSA Graphs

Detecting a Cycle in an Undirected Graph

Problem Statement

You are given an undirected graph with V vertices (labeled from 0 to V-1) and E edges. Your task is to detect if the graph contains a cycle or not.

The graph is represented as an adjacency list, where adj[i] contains all the vertices directly connected to vertex i.

Intuition – What is a Cycle?

Before diving into the solution, let’s first understand what a cycle is in an undirected graph with a simple real-world analogy.

🔹 Think of a graph like a maze of rooms connected by hallways. You start in one room and explore different paths. If you ever come back to a room you’ve already visited, there’s a loop (or cycle)!

Simple Example to Illustrate a Cycle

  1 -- 2
  |    |
  4 -- 3

Here, we can start from node 1 and explore:

  • Move to node 2
  • Move to node 3
  • Move to node 4
  • And then, uh-oh! Back to node 1 (Cycle detected! )

But Here’s the Catch!

If we always assume that revisiting a node means a cycle, we’ll make a critical mistake!

🔹 Let’s say we’re at node 1 and move to node 2.
🔹 From node 2, we move to node 1 again.
❌ Does that mean there’s a cycle? No!

Why? Because node 1 was our parent (the node we just came from). We shouldn’t consider this a cycle.

The Golden Rule for Cycle Detection

When we find a node that has already been visited, we should only consider it a cycle if it's NOT the parent of the current node.

Conclusion of Intuition

If we visit a node again and it is not the direct parent, then we have found a cycle!

Example 1

V = 5, E = 5
Edges: (0-1), (1-2), (2-3), (3-4), (4-1)

Output: Cycle Detected

Explanation: In this case, the node 1 is visited again through the path 1 → 2 → 3 → 4 → 1. Since we've reached an already visited node (other than its immediate parent in an undirected graph), a cycle is present.

Example 2

V = 4, E = 3
Edges: (0-1), (1-2), (2-3)

Output: No Cycle

Explanation: Here, as we traverse from one node to another, no node is revisited. Since no node appears again in the traversal, there is no cycle.

Intuitive Explanation of the Cycle Detection Logic

The main idea behind this code is simple: if we visit a node again while exploring the graph, and it's not the node we came from (the parent), then there must be a cycle.

🔧 How the Code Applies This Rule

  • The algorithm performs a breadth-first search (BFS) / DFS , which explores all nodes starting from a given node, one level at a time.
  • While traversing, it keeps track of:
    • Node — the current node being explored
    • Parent — the node we came from to reach the current node
  • The critical part of this code is when the algorithm checks if a node has been visited. If a neighbor of the current node has already been visited, and this neighbor is not the node we came from, it means:
    • We’ve encountered a node that was already part of our path before, but it wasn’t the one we just came from.
    • This creates a loop or cycle, because it means there's another way to reach that node — a backtrack or shortcut — forming a cycle.

Understanding the Parent Concept

Let’s break down what "parent" means and why it's important in detecting cycles.

In a graph, when you're moving from one node to another, you always have a parent node — the node you were previously at before reaching the current one. This is important because:

  • In an undirected graph, if you visit a node you’ve already seen, it might simply be the node you just came from. But that's not a cycle — it’s just a step backwards.
  • However, if you visit a node that you’ve already seen, and it’s not the node you just came from (your parent), then it means you’re revisiting that node in a different way. This forms a cycle.

Example: Understanding Parent and Cycle

Let’s go through an example to make it even clearer.

Imagine we are traversing through the graph, and we start at node 0. From node 0, we go to node 1, then to node 2, then to node 3, and finally to node 4. Now, if from node 4 we go back to node 0, we are revisiting node 0, but node 0 is the starting point. So, the parent node here is 4.

When we visit node 0, we realize it’s not the parent of node 4 (which is 4 itself), so this means we’ve found a cycle. We’re revisiting node 0 through a different path that we didn’t take before. This is how a cycle is detected.

Key Takeaways

  • Parent helps distinguish between a node we've already visited but just came back from (which isn’t a cycle) and a node we've visited through a different path (which indicates a cycle).
  • We detect a cycle when a node is revisited, and it’s not the parent of the current node.

Code Implementations

Below are the implementations in Java and C++.

BFS JAVA


import java.util.*;

class Solution {
    public boolean bfs(int start, List<List<Integer>> adj, boolean[] visited) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start, -1});
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int parent = current[1];

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(new int[]{neighbor, node});
                } 
                else if (neighbor != parent) {
                    return true; // Cycle detected
                }
            }
        }
        return false;
    }

    public boolean isCycle(int V, List<List<Integer>> adj) {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (bfs(i, adj, visited)) return true;
            }
        }
        return false;
    }
}

// Driver Code
class Main {
    public static void main(String[] args) {
        int V = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        
        adj.get(0).add(1); adj.get(1).add(0);
        adj.get(1).add(2); adj.get(2).add(1);
        adj.get(2).add(3); adj.get(3).add(2);
        adj.get(3).add(4); adj.get(4).add(3);
        adj.get(4).add(0); adj.get(0).add(4);

        Solution obj = new Solution();
        System.out.println(obj.isCycle(V, adj) ? "Cycle Found" : "No Cycle");
    }
}

Time and Space Complexity Analysis

Now that we have explored both BFS and DFS approaches for cycle detection, let's analyze their time and space complexity to understand their efficiency.

Time Complexity Analysis

  • In both BFS and DFS, we are essentially traversing the entire graph.
  • We iterate through all V vertices (in case of a disconnected graph).
  • Each edge is visited twice (once from each node’s perspective).
  • The adjacency list representation ensures that we traverse all edges in O(V + E) time.

Final Time Complexity: O(V + E) (same for BFS and DFS).

This is optimal for graph traversal algorithms.

Space Complexity Analysis

  • We store the graph as an adjacency list, which takes O(V + E) space.
  • The visited array takes O(V) space.
  • BFS uses a queue (O(V) in the worst case).
  • DFS uses recursion stack space (O(V) in the worst case).

Final Space Complexity: O(V + E) (for both BFS and DFS).

Recent Posts